package day230321;


/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/3/22 21:50
 * 众数思路
 */
public class Main21 {

    public static void main(String[] args) {
        int[] array = {1,2,3,2,2,2,5,4,2};
        int ret = new Solution1().MoreThanHalfNum_Solution(array);
        System.out.println(ret);
    }

}

class Solution1 {
    /**
     * 遍历数组, 如果后面的数与 mode 相同, 则迭代次数, 如果不同, 则次数递减, 当为 0 时更改 mode
     * 如果众数存在, 则为 mode
     * 然后确认 mode 是否次数超过数组的一半
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // 边界判断
        if (numbers == null || numbers.length == 0) {
            return 0;
        }
        int mode = numbers[0]; // 存储可能的众数
        int count = 1; // 记录 mode 出现的次数
        // 遍历数组
        for (int i = 1; i < numbers.length; i++) {
            if (count > 0) {
                // 如果次数大于0
                if (numbers[i] == mode) {
                    count++; // 如果是同一个数字, 则增加次数
                } else {
                    count--;
                }
            } else {
                // 此时说明前一个 mode 已经被抵消, 需要更新  mode 和 count
                mode = numbers[i];
                count = 1;
            }
        }
        // 验证出现的次数是否大于数组的一半
        count = 0;
        for (int number : numbers) {
            if (number == mode) {
                count++;
            }
        }
        return count > numbers.length / 2 ? mode : 0; // 将结果返回
    }
}
